package com.acwing.www;

/**
 * Creared with IntelliJ IDEA.
 * Description:不用作比较的排序
 * 计数排序：一组有确定范围的序列（maxVal - minVal + 1）定义一个数组这个就是数组范围，起始值下标就是i - minVal然后再把所有数字出现的次数记录下来，再循环放入数组就有序了
 * 基数排序:可以定义十个队列 每一个数的每一位数，先看个位数的数字放入相对应的队列中，然后在出队，此时个位数就有序了，然后再看十位数，一样的操作，直至所有数有序
 * 桶排序:确定每个桶的取值范围，将所有数字按相应的取值范围放入桶内，然后把所有的桶按顺序排好，再把里面的所有数字拿出来，然后所有数就有序了
 * User:yxd
 * Date:2022-01-25
 * Time:21:02
 */
public class NoComparison {
    public static void countingSort(int[] array){//时间复杂度O(N)空间复杂度O(M)M代表了数组范围
        // 稳定性 ：此时的代码是不稳定的，但本质是稳定的，可以在定义一个数组来保证重复数据不改变原始位置
        int minVal = array[0];
        int maxVal = array[0];
        for (int i = 0; i < array.length; i++) {
            if(minVal > array[i]){
                minVal = array[i];//找最小值
            }
            if(maxVal < array[i]){
                maxVal = array[i];//找最大值
            }
        }
        int[] tmp = new int[maxVal - minVal + 1];

        //统计序列当中所有数字出现的次数
        for (int i = 0; i < tmp.length; i++) {
            int index = array[i];
            tmp[index - minVal] ++;//为了合理利用空间
        }
        int indexArray = 0;
        for (int i = 0; i < tmp.length; i++) {
            while (tmp[i] > 0){
                //这里一定要加minVal,因为tmp里面放的就是下标减去minVal，所以要加上
                array[indexArray] = i + minVal;
                tmp[i] --;
                indexArray ++;
            }
        }
    }
}
